package sort;

import java.util.Arrays;

/**
 * 工作原理：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
 * 平均 O(nlogn)
 * 最好 O(nlogn)
 * 最坏 O(n2)
 * 空间 O(logn)
 * 排序方式 in-place
 * 稳定性 不稳定
 */
public class Quick {
    private int [] a = {1,6,2,4,1,5,9};

    private void sort(){
        quickSort(a, 0, a.length - 1);
    }

    private void quickSort(int [] a, int l, int r) {
        int i = l;
        int j = r;
        if (i >= j) {
            return;
        }
        int key = a[i];
        while(i < j){
            while(i < j && a[j] >= key){
                j --;
            }
            a[i] = a[j];
            while(i < j && a[i] <= key){
                i ++;
            }
            a[j] = a[i];
        }
        a[i] = key;
        quickSort(a, l, i - 1);
        quickSort(a, j + 1, r);
    }

    private void print(){
        System.out.println(Arrays.toString(a));
    }

    public static void main(String [] args){
        Quick maoPao = new Quick();
        maoPao.print();
        maoPao.sort();
        maoPao.print();
    }
}
